1. 题目描述（简单难度）
[success] 100. 相同的树
2. 解法一：遍历树
使用树的先序遍历，将遍历结果拼接，比较结果是否相同
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
StringBuilder sb = new StringBuilder();
StringBuilder sb1 = new StringBuilder();
preOrderRecur(p,sb);
preOrderRecur(q,sb1);
if(sb.toString().equals(sb1.toString())){
return true;
}
return false;
}
public void preOrderRecur(TreeNode root,StringBuilder sb){
if(root == null){
sb.append("-1");
return;
}
sb.append(root.val);
preOrderRecur(root.left,sb);
preOrderRecur(root.right,sb);
}
}
3. 解法二：深度优先搜索
如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
else if(p == null || q==null){
return false;
}
else if(p.val != q.val){
return false;
}
else{
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
}